﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    public class WordSearch
    {
        public bool Exist(char[][] board, string word)
        {
            var m = board.Length;
            var n = board[0].Length;
            var checkedChars = new bool[m, n];
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (!checkedChars[i, j])
                    {
                        var indexOfChar = word.IndexOf(board[i][j]);
                        if (indexOfChar >= 0)
                        {
                            var matchChars = GetMatchChars(board, i, j, indexOfChar, word, board[i][j].ToString());
                            if (matchChars == word)
                            {
                                return true;
                            }
                            //else
                            //{
                            //    checkedChars[i, j] = true;
                            //}
                        }
                    }
                }
            }
            return false;
        }
        public class Cell
        {
            public char Char { get; set; }
            public int i { get; set; }
            public int j { get; set; }
        }
        public static List<Cell> GetStep1Cells(char[][] board, int i, int j,char targetChar, bool[,] usedCells)
        {
            var result = new List<Cell> ();
            if (i - 1 > -1)
            {
                var cellTop = board[i - 1][j];
                if (targetChar== cellTop && !usedCells[i - 1,j])
                {
                    result.Add(new Cell() { Char = cellTop, i = i - 1, j = j });
                }
            }
            if (i + 1 < board.Length)
            {
                var cellDown = board[i + 1][j];
                if (targetChar == cellDown && !usedCells[i + 1,j])
                    result.Add(new Cell() { Char = cellDown, i = i + 1, j = j });
            }
            

            if (j - 1 > -1)
            {
                var cellLeft = board[i ][j-1];
                if (targetChar == cellLeft && !usedCells[i,j-1])
                    result.Add(new Cell() { Char = cellLeft, i = i , j = j-1 });
            }
            
            if (j + 1 < board[0].Length)
            {
                var cellRight = board[i][j+1];
                if (targetChar == cellRight && !usedCells[i,j+1])
                    result.Add(new Cell() { Char = cellRight, i = i, j = j + 1 });
            }
            return result;
        }
        public static string GetMatchChars(char[][] board, int i, int j,int indexOfChar, string word,string currentChars)
        {
            var m = board.Length;
            var n = board[0].Length;
            var leftMacthChars="";
            var rightMacthChars="";
            //var indexOfChar1 = word.IndexOf(board[i][j],);
            var usedCells = new bool[board.Length, board[0].Length];
            usedCells[i,j] = true;
            if (indexOfChar > 0)
            {
                leftMacthChars = GetLeftMacthChars(board,i,j,indexOfChar-1,word,"", word.Substring(0,indexOfChar), usedCells);
            }
            if (indexOfChar < word.Length - 1)
            {
                rightMacthChars = GetRightMacthChars(board, i, j, indexOfChar+1, word, "",word.Substring(indexOfChar+1), usedCells);
            }
            return leftMacthChars+ currentChars+ rightMacthChars;
        }
        public static string GetLeftMacthChars(char[][] board, int i, int j, int indexOfChar, string word, string currentChars, string endString, bool[,] usedCell)
        {
            if (indexOfChar <= 0)
            {
                return currentChars;
            }
            else
            {

                var targetChar = word[indexOfChar];
                var step1Chars = GetStep1Cells(board, i, j, targetChar, usedCell);

               // var step1CharF = step1Chars.Where(x => x.Char == targetChar && !usedCell.Any(u=>u.i==x.i&& u.j==x.j));
                foreach (var step1Char in step1Chars)
                {
                    var tempChars = currentChars;
                    currentChars = step1Char.Char+currentChars;
                    usedCell[step1Char.i, step1Char.j]=true;
                    currentChars = GetLeftMacthChars(board, step1Char.i, step1Char.j, indexOfChar - 1, word, currentChars, endString, usedCell);
                    if (currentChars == endString)
                    {
                        return currentChars;
                    }
                    else
                    {
                        usedCell[step1Char.i, step1Char.j] = false;
                        currentChars = tempChars;
                    }
                }
                
                return currentChars;
            }
        }
        public static string GetRightMacthChars(char[][] board, int i, int j, int indexOfChar, string word, string currentChars,string endString, bool[,] usedCell)
        {
            if (indexOfChar > word.Length-1)
            {
                return currentChars;
            }
            else
            {
                var targetChar = word[indexOfChar];
                var step1Chars = GetStep1Cells(board, i, j, targetChar,usedCell);

                foreach (var step1Char in step1Chars)
                {
                    var tempChars = currentChars;
                    currentChars = currentChars + step1Char.Char;
                    usedCell[step1Char.i, step1Char.j] = true;
                    currentChars = GetRightMacthChars(board, step1Char.i, step1Char.j, indexOfChar + 1, word, currentChars, endString,usedCell);
                    if (currentChars== endString)
                    {
                       return currentChars;
                    }
                    else
                    {
                        usedCell[step1Char.i, step1Char.j] = false;
                        currentChars = tempChars;
                    }
                }
                
                return currentChars;
            }
        }
    }
}
